package q886_possibleBipartition;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    /*
    可能的二分法
    通过DFS来解决
    首先利用一个g来存储每一个人不喜欢的人的list
    然后假设将人群染色为1或者2两种颜色
    那么每次进入dfs时，开始考虑当前人是否已经与其不喜欢的人同色，那么返回false
    否则从当前人不喜欢的人中进行dfs，并且不喜欢的人必然是不同色的，所以
    要用3 ^ color来变换当前颜色(3 ^ 1 = 2, 3 ^ 2 = 1)
     */
    public boolean possibleBipartition(int n, int[][] dislikes) {
        int[] colors = new int[n + 1];
        List<Integer>[] g = new List[n + 1];
        for (int i = 0; i <= n; ++i) {
            g[i] = new ArrayList<>();
        }
        for (int[] dislike : dislikes) {
            g[dislike[0]].add(dislike[1]);
            g[dislike[1]].add(dislike[0]);
        }
        for (int i = 1; i <= n; i++) {
            if (colors[i] == 0 && !dfs(i, 1, colors, g)) {
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int idx, int color, int[] colors, List<Integer>[] g) {
        colors[idx] = color;
        for (int i : g[idx]) {
            if (colors[i] != 0 && colors[i] == colors[idx]) {
                return false;
            }
            if (colors[i] == 0 && !dfs(i, 3 ^ color, colors, g)) {
                return false;
            }
        }
        return true;
    }
}
